//1.堆--优先级队列----自己写一个堆
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> ret;
        for(auto& e: nums) {
            ret.push(e);
        }
        for(int i=1;i<k;++i) {
            ret.pop();
        }
        return ret.top();
    }
};
//如果patition和nums[i]相等，则会导致i持续增加，最后导致枢纽划分到重复元素的末尾，显而易见对于快速排序如果枢纽划分到中间在理论上是最优的，因为它最小化了递归的深度。
//2. On做法
//一定要保证枢纽尽量在中间保证时间复杂度,遍历元素个数从n,n/2,n/4,平均时间复杂度变成了On
//要是重复元素过多，那么遍历元素个数从n,n-1,n-2,...  最坏时间复杂度变成了On^2
//https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/2361969/215-shu-zu-zhong-de-di-k-ge-zui-da-yuan-d786p/
class Solution {
public:
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (nums[right] >= pivot && left < right) {
                if(nums[right] == pivot) {
                    right --;
                    break;
                }
                right--;
            }
            nums[left] = nums[right];
            while (nums[left] <= pivot && left < right) {
                if(nums[left] == pivot) {
                    left ++;
                    break;
                }
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
    int qsort(vector<int>& nums, int left, int right, int k) {
        int pivot = partition(nums, left, right);
        if (pivot == k) {
            return nums[pivot];
        } else if (pivot < k) {
            return qsort(nums, pivot + 1, right, k);
        } else {
            return qsort(nums, left, pivot - 1, k);
        }
        return -1;
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return qsort(nums, 0, n - 1, n - k);
    }
};


//3.三路划分---On做法
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, k);
    }
    int quickSelect(vector<int>& nums, int k) {
        // 基于快排的快速选择
        // 随机选择基准数字
        int p = nums[rand() % nums.size()];
        // 将大于等于小于的元素分别放入三个数组
        vector<int> big, equal, small;
        for (int a : nums) {
            if (a < p) 
                small.push_back(a);
            else if (a == p) 
                equal.push_back(a);
            else 
                big.push_back(a);
        }
        // 第k大元素在big中, 递归划分
        if (k <= big.size()) {
            return quickSelect(big, k);
        }
        // 第k大元素在small中, 递归划分
        if (big.size() + equal.size() < k) {
            return quickSelect(small, k - (big.size() + equal.size()));
        }
        // 第k大元素在equal中, 返回p
        return p;
    }
};